package com.gitee.wsl.transform.encode.pinyin.interval

class IntervalNode(intervals: List<Intervalable>) {
    enum class Direction {
        LEFT, RIGHT
    }

    private var left: IntervalNode? = null
    private var right: IntervalNode? = null
    private var point: Int
    private val intervals = ArrayList<Intervalable>()

    init {
        this.point = determineMedian(intervals)

        val toLeft = ArrayList<Intervalable>()
        val toRight = ArrayList<Intervalable>()

        for (interval in intervals) {
            if (interval.end  < this.point) {
                toLeft.add(interval)
            } else if (interval.start > this.point) {
                toRight.add(interval)
            } else {
                this.intervals.add(interval)
            }
        }

        if (toLeft.isNotEmpty()) {
            this.left = IntervalNode(toLeft)
        }
        if (toRight.isNotEmpty()) {
            this.right = IntervalNode(toRight)
        }
    }

    fun determineMedian(intervals: List<Intervalable>): Int {
        var start = -1
        var end = -1
        for (interval in intervals) {
            val currentStart: Int = interval.start
            val currentEnd: Int = interval.end
            if (start == -1 || currentStart < start) {
                start = currentStart
            }
            if (end == -1 || currentEnd > end) {
                end = currentEnd
            }
        }
        return (start + end) / 2
    }

    fun findOverlaps(interval: Intervalable): List<Intervalable> {
        val overlaps = ArrayList<Intervalable>()

        if (this.point < interval.start) {
            // Tends to the right
            addToOverlaps(interval, overlaps, findOverlappingRanges(this.right, interval))
            addToOverlaps(interval, overlaps, checkForOverlapsToTheRight(interval))
        } else if (this.point > interval.end) {
            // Tends to the left
            addToOverlaps(interval, overlaps, findOverlappingRanges(this.left, interval))
            addToOverlaps(interval, overlaps, checkForOverlapsToTheLeft(interval))
        } else {
            // Somewhere in the middle
            addToOverlaps(interval, overlaps, this.intervals)
            addToOverlaps(interval, overlaps, findOverlappingRanges(this.left, interval))
            addToOverlaps(interval, overlaps, findOverlappingRanges(this.right, interval))
        }

        return overlaps
    }

    protected fun addToOverlaps(
        interval: Intervalable,
        overlaps: MutableList<Intervalable>,
        newOverlaps: List<Intervalable>
    ) {
        for (currentInterval in newOverlaps) {
            if (currentInterval != interval) {
                overlaps.add(currentInterval)
            }
        }
    }

    protected fun checkForOverlapsToTheLeft(interval: Intervalable): List<Intervalable> {
        return checkForOverlaps(interval, Direction.LEFT)
    }

    protected fun checkForOverlapsToTheRight(interval: Intervalable): List<Intervalable> {
        return checkForOverlaps(interval, Direction.RIGHT)
    }

    protected fun checkForOverlaps(
        interval: Intervalable,
        direction: Direction
    ): List<Intervalable> {
        val overlaps = ArrayList<Intervalable>()

        for (currentInterval in this.intervals) {
            when (direction) {
                Direction.LEFT -> if (currentInterval.start<= interval.end) {
                    overlaps.add(currentInterval)
                }

                Direction.RIGHT -> if (currentInterval.end >= interval.start) {
                    overlaps.add(currentInterval)
                }
            }
        }

        return overlaps
    }

    protected fun findOverlappingRanges(node: IntervalNode?, interval: Intervalable): List<Intervalable> {
        return node?.findOverlaps(interval) ?: emptyList()
    }
}
